Search results for "Spanning tree"
showing 10 items of 53 documents
Combined column-and-row-generation for the optimal communication spanning tree problem
2018
Abstract This paper considers the exact solution of the optimal communication spanning tree problem (OCSTP), which can be described as follows: Given an undirected graph with transportation costs on every edge and communication requirements for all pairs of vertices, the OCSTP seeks for a spanning tree that minimizes the sum of the communication costs between all pairs of vertices, where the communication cost of a pair of vertices is defined as their communication requirement multiplied by the transportation cost of the unique tree path that connects the two vertices. Two types of compact formulations for OCSTP were presented in the literature. The first one is a four-index model based on …
Automatic detection of hemangiomas using unsupervised segmentation of regions of interest
2016
In this paper we compare the performances of three automatic methods of identifying hemangioma regions in images: 1) unsupervised segmentation using the Otsu method, 2) Fuzzy C-means clustering (FCM) and 3) an improved region growing algorithm based on FCM (RG-FCM). For each image, the starting point of the algorithms is a rectangular region of interest (ROI) containing the hemangioma. For computing the performances of each method, the ROIs had been manually labeled in 2 classes: pixels of hemangioma and pixels of non-hemangioma. The computed scores are given separately for each image, as well as global performances across all ROIs for both classes. The best classification of non-hemangioma…
Efficient Online Laplacian Eigenmap Computation for Dimensionality Reduction in Molecular Phylogeny via Optimisation on the Sphere
2019
Reconstructing the phylogeny of large groups of large divergent genomes remains a difficult problem to solve, whatever the methods considered. Methods based on distance matrices are blocked due to the calculation of these matrices that is impossible in practice, when Bayesian inference or maximum likelihood methods presuppose multiple alignment of the genomes, which is itself difficult to achieve if precision is required. In this paper, we propose to calculate new distances for randomly selected couples of species over iterations, and then to map the biological sequences in a space of small dimension based on the partial knowledge of this genome similarity matrix. This mapping is then used …
The node-depth encoding
2008
The node-depth encoding has elements from direct and indirect encoding for trees which encodes trees by storing the depth of nodes in a list. Node-depth encoding applies specific search operators that is a typical characteristic for direct encodings. An investigation into the bias of the initialization process and the mutation operators of the node-depth encoding shows that the initialization process has a bias to solutions with small depths and diameters, and a bias towards stars. This investigation, also, shows that the mutation operators are unbiased. The performance of node-depth encoding is investigated for the bounded-diameter minimum spanning tree problem. The results are presented f…
Orientation matters
2008
The optimal communication spanning tree (OCST) problem is a well known $\mathcal{NP}$-hard combinatorial optimization problem which seeks a spanning tree that satisfies all given communication requirements for minimal total costs. It has been shown that optimal solutions of OCST problems are biased towards the much simpler minimum spanning tree (MST) problem. Therefore, problem-specific representations for EAs like heuristic variants of edge-sets that are biased towards MSTs show high performance.In this paper, additional properties of optimal solutions for Euclidean variants of OCST problems are studied. Experimental results show that not only edges in optimal trees are biased towards low-…
Counting degree sequences of spanning trees in bipartite graphs: A graph‐theoretic proof
2019
A new image segmentation approach using community detection algorithms
2015
Image segmentation has an important role in many image processing applications. Several methods exist for segmenting an image. However, this technique is still a relatively open topic for which various research works are regularly presented. With the recent developments on complex networks theory, image segmentation techniques based on graphs has considerably improved. In this paper, we present a new perspective of image segmentation, by applying three of the most efficient community detection algorithms, Louvain, infomap and stability optimization based on the louvain algorithm, and we extract communities in which the highest modularity feature is achieved. After we show that this measure …
On utilizing dependence-based information to enhance micro-aggregation for secure statistical databases
2011
Published version of an article in the journal: Pattern Analysis and Applications. Also available from the publisher at: http://dx.doi.org/10.1007/s10044-011-0199-9 We consider the micro-aggregation problem which involves partitioning a set of individual records in a micro-data file into a number of mutually exclusive and exhaustive groups. This problem, which seeks for the best partition of the micro-data file, is known to be NP-hard, and has been tackled using many heuristic solutions. In this paper, we would like to demonstrate that in the process of developing micro-aggregation techniques (MATs), it is expedient to incorporate information about the dependence between the random variable…
On the low-dimensional Steiner minimum tree problem in Hamming metric
2013
While it is known that the d-dimensional Steiner minimum tree problem in Hamming metric is NP-complete if d is part of the input, it is an open question whether this also holds for fixed dimensions. In this paper, this question is answered by showing that the Steiner minimum tree problem in Hamming metric is already NP-complete in 3 dimensions. Furthermore, we show that, the minimum spanning tree gives a 2-2d approximation on the Steiner minimum tree for d>=2. Using this result, we analyse the so-called k-LCA and A"k approximation algorithms and show improved approximation guarantees for low dimensions.
Tree automata, tree decomposition and hyperedge replacement
2005
Recent results concerning efficient solvability of graph problems on graphs with bounded tree-width and decidability of graph properties for hyperedge-replacement graph grammars are systematised by showing how they can be derived from recognisability of corresponding tree classes by finite tree automata, using only well-known techniques from tree-automata theory.